import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/7 9:45
 * @description 中心扩展，遍历，以一个单词扩展，或以两个单词扩展，
 */
public class Solution3 {
    public static void main(String[] args) {

    }
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        char[]  S = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(S, i, i);
            int len2 = expandAroundCenter(S, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(char[] s, int left, int right) {
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}
